'''
https://leetcode.cn/problems/parallel-courses
'''
from collections import deque
from typing import List


class Solution:
    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:
        graph = [[] for _ in range(n + 1)]
        indegrees = [0] * (n + 1)
        for u, v in relations:
            graph[u].append(v)
            indegrees[v] += 1

        q = deque([u for u in range(1, n + 1) if indegrees[u] == 0])
        semester = 0
        n_course = 0
        while q:
            semester += 1
            for _ in range(len(q)):
                u = q.popleft()
                n_course += 1
                for v in graph[u]:
                    indegrees[v] -= 1
                    if indegrees[v] == 0:
                        q.append(v)
        return semester if n_course == n else -1
